package codetop.microsoft.T298;

import java.util.PriorityQueue;
import java.util.Queue;

class MedianFinder {

    private Queue<Integer> large = new PriorityQueue<>((a, b) -> (a - b));
    private Queue<Integer> small = new PriorityQueue<>((a, b) -> (b - a));

    public MedianFinder() {
    }

    public void addNum(int num) {
        if (small.size() == large.size()) {
            large.offer(num);
            small.offer(large.poll());
        } else {
            small.offer(num);
            large.offer(small.poll());
        }
    }

    public double findMedian() {
        if (small.size() == large.size())
            return (small.peek() + large.peek()) / 2.0;
        return small.peek();
    }
}